/**
  To change this template, choose Tools | Templates
  and open the template in the editor.
*/
package mylist;

import interfaces.MyMap;
import interfaces.MyMap.Entry;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**

@author Daryna_Ragimova
 */
public class MyTreeMap<K, V> implements MyMap<K, V> {

    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private final Comparator<? super K> comparator;
    private SimpleEntry<K, V> root = null;
    private int size = 0;

    /**
    constructs a new, empty tree map, using the natural ordering of its keys
     */
    public MyTreeMap() {
        comparator = null;
    }

    /**
    constructs a new, empty tree map, ordered according to the given 
    comparator
    @param comparator - the comparator that will be used to order this map
     */
    public MyTreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    @Override
    public void clear() {
        size = 0;
        root = null;
    }

    @Override
    public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }

    private SimpleEntry<K, V> getFirstEntry() {
        SimpleEntry<K, V> p = root;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
        }
        return p;
    }

    private <K, V> SimpleEntry<K, V> findNextEntry(SimpleEntry<K, V> current) {
        if (current == null) {
            return null;
        } else if (current.right == null) {
            SimpleEntry<K, V> p = current.parent;
            SimpleEntry<K, V> child = current;
            while (p != null && child == p.right) {
                child = p;
                p = p.parent;
            }
            return p;
            
        } else {
            SimpleEntry<K, V> p = current.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
    }


    @Override
    public boolean containsValue(Object value) {
        for (SimpleEntry<K, V> e = getFirstEntry(); e != null; findNextEntry(e)) {
            if (e.value == null ? value == null : e.value.equals(value)) {
                return true;
            }
        }
        return false;
    }

    public SimpleEntry<K, V> getEntry(Object key) {
        if (key == null) {
            throw new NullPointerException();
        }
        if (comparator != null) {
            K k = (K) key;

            SimpleEntry<K, V> p = root;
            while (p != null) {
                int cmp = comparator.compare(k, p.key);
                if (cmp < 0) {
                    p = p.left;
                } else if (cmp > 0) {
                    p = p.right;
                } else {
                    return p;
                }
            }
            return null;
        }
        Comparable<? super K> k = (Comparable<? super K>) key;
        SimpleEntry<K, V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0) {
                p = p.left;
            } else if (cmp > 0) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }

    @Override
    public V get(Object key) {
        SimpleEntry<K, V> p = getEntry(key);
        return (p == null ? null : p.value);
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private void rotateLeft(SimpleEntry x) {
        if (x != null) {
            SimpleEntry y = x.right;
            x.right = y.left;
            if (y.left != null) {
                y.left.parent = x;
            }

            if (y != null) {
                y.parent = x.parent;
            }
            if (x.parent != null) {
                if (x == x.parent.left) {
                    x.parent.left = y;
                } else {
                    x.parent.right = y;
                }
            } else {
                root = y;
            }
            y.left = x;
            x.parent = y;
        }
    }

    private void rotateRight(SimpleEntry x) {
        if(x != null){
            SimpleEntry y = x.left;
            x.left = y.right;
            if (y.right != null) {
                y.right.parent = x;
            }

            if (y != null) {
                y.parent = x.parent;
            }
            if (x.parent != null) {
                if (x == x.parent.right) {
                    x.parent.right = y;
                } else {
                    x.parent.left = y;
                }
            } else {
                root = y;
            }
            y.right = x;
            x.parent = y;
        }
    }

    private void insertFixup(SimpleEntry x) {
        while (x != root && x.parent.color == RED && x != null) {
            if (x.parent == x.parent.parent.left) {
                SimpleEntry y = x.parent.parent.right;
                if (y.color == RED) {
                    x.parent.color = BLACK;
                    y.color = BLACK;
                    x.parent.parent.color = RED;
                    x = x.parent.parent;
                } else {

                    // uncle is BLACK 
                    if (x == x.parent.right) {
                        // make x a left child 
                        x = x.parent;
                        rotateLeft(x);
                    }

                    // recolor and rotate 
                    x.parent.color = BLACK;
                    x.parent.parent.color = RED;
                    rotateRight(x.parent.parent);
                }
            } else {

                // mirror image of above code 
                SimpleEntry y = x.parent.parent.left;
                if (y.color == RED) {

                    // uncle is RED 
                    x.parent.color = BLACK;
                    y.color = BLACK;
                    x.parent.parent.color = RED;
                    x = x.parent.parent;
                } else {

                    // uncle is BLACK 
                    if (x == x.parent.left) {
                        x = x.parent;
                        rotateRight(x);
                    }
                    x.parent.color = BLACK;
                    x.parent.parent.color = RED;
                    rotateLeft(x.parent.parent);
                }
            }
        }
        root.color = BLACK;
    }

    @Override
    public V put(K key, V value) {
        if (root == null){
                root = new SimpleEntry<K, V>(key,value,null);
                size++;
                return null;
        }
        
        SimpleEntry<K, V> current, parent;
        // allocate SimpleEntry for data and insert in tree  
        // find where SimpleEntry belongs 
        current = root;
        parent = root;
        
        while (current != null) {
            parent = current;
            if (comparator != null){
                int resultOfComparison = comparator.compare(key, current.key);
                if (resultOfComparison == 0){
                    V valueToReturn = current.value;
                    current.value = value;
                    return valueToReturn;
                }
                current = resultOfComparison < 0 ? current.left : current.right;
            }else{
                Comparable<? super K> k = (Comparable<? super K>) key;
                int resultOfComparison =k.compareTo(current.key); 
                if (resultOfComparison == 0){
                    V valueToReturn = current.value;
                    current.value = value;
                    return valueToReturn;
                }
                current = resultOfComparison < 0 ? current.left : current.right;
            }
        }
        SimpleEntry<K, V> x = new SimpleEntry<K, V>(key,value,parent);
        x.color = RED;
        size++;
        // insert SimpleEntry in tree 
        if (comparator != null){
                if (comparator.compare(key, parent.key) < 0)
                    parent.left = x;
                else
                    parent.right = x;
            }else{
                Comparable<? super K> k = (Comparable<? super K>) key;
                if (k.compareTo(parent.key) < 0)
                    parent.left = x;
                else
                    parent.right = x;
                }
        insertFixup(x);
        return null;
    }
    
    private void deleteFixup(SimpleEntry x) {
    while (x != root && x.color == BLACK) {
        if (x == x.parent.left) {
            SimpleEntry w = x.parent.right;
            if (w.color == RED) {
                w.color = BLACK;
                x.parent.color = RED;
                rotateLeft (x.parent);
                w = x.parent.right;
            }
            if (w.left.color == BLACK && w.right.color == BLACK) {
                w.color = RED;
                x = x.parent;
            } else {
                if (w.right.color == BLACK) {
                    w.left.color = BLACK;
                    w.color = RED;
                    rotateRight (w);
                    w = x.parent.right;
                }
                w.color = x.parent.color;
                x.parent.color = BLACK;
                w.right.color = BLACK;
                rotateLeft (x.parent);
                x = root;
            }
        } else {
            SimpleEntry w = x.parent.left;
            if (w.color == RED) {
                w.color = BLACK;
                x.parent.color = RED;
                rotateRight (x.parent);
                w = x.parent.left;
            }
            if (w.right.color == BLACK && w.left.color == BLACK) {
                w.color = RED;
                x = x.parent;
            } else {
                if (w.left.color == BLACK) {
                    w.right.color = BLACK;
                    w.color = RED;
                    rotateLeft (w);
                    w = x.parent.left;
                }
                w.color = x.parent.color;
                x.parent.color = BLACK;
                w.left.color = BLACK;
                rotateRight (x.parent);
                x = root;
            }
        }
    }
    x.color = BLACK;
}
    
    @Override
    public V remove(K key) {
       SimpleEntry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        V oldValue = p.value;
        deleteEntry(p);
        return oldValue; 
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<MyMap.Entry<K, V>> entryIterator() {
        return new EntryIterator(getFirstEntry());
    }

    private void deleteEntry(SimpleEntry<K, V> p) {
        
        SimpleEntry<K, V> x = null;
        SimpleEntry<K, V> y = null;
        if (p == null) {
            return;
        }
        if (p.left == null || p.right == null) {
            //y has a null node as a child 
            y = p;
        } else {
            // find tree findNextEntry with a null node as a child
            y = p.right;
            while (y.left != null) {
                y = y.left;
            }
        }

        // x is y's only child 
        if (y.left != null) {
            x = y.left;
        } else {
            x = y.right;
        }

        // remove y from the parent chain 
        x.parent = y.parent;
        if (y.parent != null) {
            if (y == y.parent.left) {
                y.parent.left = x;
            } else {
                y.parent.right = x;
            }
        } else {
            root = x;
        }

        if (y != p) {
            p.value = y.value;
        }


        if (y.color == BLACK) {
            deleteFixup(x);
        }
    }

    class SimpleEntry<K, V> implements MyMap.Entry<K, V> {

        K key;
        V value;
        SimpleEntry<K, V> left = null;
        SimpleEntry<K, V> right = null;
        SimpleEntry<K, V> parent;
        boolean color = BLACK;

        SimpleEntry(K key, V value, SimpleEntry<K, V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
    }

    abstract class AbstractEntryIterator<T> implements Iterator<T> {

        SimpleEntry<K, V> next;
        SimpleEntry<K, V> lastReturned;

        AbstractEntryIterator(SimpleEntry<K, V> first) {
            lastReturned = null;
            next = first;
        }

        @Override
        public final boolean hasNext() {
            return next != null;
        }

        SimpleEntry<K, V> nextEntry() {
            SimpleEntry<K, V> e = next;
            if (e == null) {
                throw new NoSuchElementException();
            }
            next = findNextEntry(e);
            lastReturned = e;
            return e;
        }

        @Override
        public void remove() {
            if (lastReturned == null) {
                throw new IllegalStateException();
            }
            if (lastReturned.left != null && lastReturned.right != null) {
                next = lastReturned;
            }
            deleteEntry(lastReturned);
            lastReturned = null;
        }
    }

    final class EntryIterator extends AbstractEntryIterator<MyMap.Entry<K, V>> {

        EntryIterator(SimpleEntry<K, V> first) {
            super(first);
        }

        @Override
        public MyMap.Entry<K, V> next() {
            return nextEntry();
        }
    }
}
